This invention relates to the compression of binary data and more particularly to an improved run-length coding circuit.
There is a need in electronic systems for compacting data so that the information contained within said data may be stored in less memory or transmitted at a higher rate.
One technique is the use of a simple run-length code where the number of bits is transmitted rather than the bits themselves. In other words, the number "64" would be transmitted instead of the 64 bits.
A predictor may be used before the run-length encoder to increase the compression. A predictor examines the previous bits and then predicts the state of the instant bit. The prediction and the instant bit are then compared, a successful prediction being coded as a "0" bit, an unsuccessful prediction being coded as a "1" bit. A well designed predictor increases the average run length and, therefore, improves the efficiency of the encoder. In the system described herein a predictor is used ahead of the encoder but the claims are directed to the encoder alone since the encoder may be used with or without the predictor in any actual transmission or recording system.
A problem with a simple run-length encoder is that it must process each input bit as it is received. For example, after the reception of a string of 0's, the next bit must be inspected. If it is a 0, a run-length counter is incremented; if it is a one, the previous counter total is transmitted and the counter is initialized.
To speed up the data rate, the run-length encoder may be designed to process data bits in parallel. One example of this technique is described by John Monk in U.S. Pat. No. 3,588,329. The input bits are inspected in blocks of 64, 16 or 4 bits at a time and a variable length output word is produced containing the compressed data in the form of modified run-lengths.
The parallel processing of data in the form of data blocks increases the data rate, but ultimately a limit is reached based on the number of bits per block, which must be optimized for the particular application, and the circuit complexity, which must be minimized. An example of a commercially useful encoder is one that can operate in excess of 50 M bits per second in the compression of image data.